// https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/

// 算法思路总结：
// 1. 使用前缀和与哈希表统计可被K整除的子数组
// 2. 计算前缀和模K的余数并处理负数情况
// 3. 相同余数之间的子数组和可被K整除
// 4. 统计相同余数出现的频率进行计数
// 5. 时间复杂度：O(n)，空间复杂度：O(k)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_map>

class Solution 
{
public:
    int subarraysDivByK(vector<int>& nums, int k) 
    {
        int m = nums.size();
        unordered_map<int, int> up;
        up[((0 % k) + k) % k] = 1;

        int ret = 0, sum = 0;
        for (int i = 0 ; i < m ; i++)
        {
            sum += nums[i];
            int target = ((sum % k) + k) % k;

            if (up.count(target) > 0)
            {
                ret += up[target];
            }
            
            up[target]++;
        }

        return ret;
    }
};

int main()
{
    vector<int> nums1 = {4,5,0,-2,-3,1}, nums2 = {5};
    int k1 = 5, k2 = 9;

    Solution sol;

    cout << sol.subarraysDivByK(nums1, k1) << endl; 
    cout << sol.subarraysDivByK(nums2, k2) << endl;

    return 0;
}